home *** CD-ROM | disk | FTP | other *** search
/ CU Amiga Super CD-ROM 19 / CU Amiga Magazine's Super CD-ROM 19 (1998)(EMAP Images)(GB)[!][issue 1998-02].iso / CUCD / Programming / LEDA / source / src / dict / _rb_tree.c < prev    next >
Encoding:
C/C++ Source or Header  |  1994-11-16  |  4.9 KB  |  179 lines
  1. /*******************************************************************************
  2. +
  3. +  LEDA  3.1c
  4. +
  5. +
  6. +  _rb_tree.c
  7. +
  8. +
  9. +  Copyright (c) 1994  by  Max-Planck-Institut fuer Informatik
  10. +  Im Stadtwald, 6600 Saarbruecken, FRG     
  11. +  All rights reserved.
  12. + 
  13. *******************************************************************************/
  14.  
  15.  
  16. #include <LEDA/impl/rb_tree.h>
  17.  
  18.  
  19. //----------------------------------------------------------------------------
  20. //  rb_tree:
  21. //
  22. //  rebalancing routines for red black trees
  23. //
  24. //----------------------------------------------------------------------------
  25.  
  26.  
  27. void rb_tree::insert_rebal(rb_tree_item v)
  28. {
  29.   // preconditions:  v is new node created by insertion
  30.   //                 v != root
  31.   //
  32.   //                    u
  33.   //                    |
  34.   //                    v
  35.   //                   / \
  36.   //                  x   y
  37.   //
  38.  
  39.   rb_tree_item u = v->parent;
  40.  
  41.   while (u->get_bal() == red)
  42.   {
  43.     int dir = (v == u->child[left]) ? left : right;
  44.  
  45.     rb_tree_item p = u->parent; 
  46.     int dir1 = (u == p->child[left]) ? left : right;
  47.  
  48.     rb_tree_item w = p->child[1-dir1];
  49.  
  50.     if ( w->get_bal() == red )    // p has two red children (u and w)
  51.        { u->set_bal(black);
  52.          w->set_bal(black);
  53.          if (p == root())  
  54.          { p->set_bal(black); 
  55.            break; 
  56.           }
  57.          p->set_bal(red);
  58.          v = p;
  59.          u = p->parent;
  60.         }
  61.     else 
  62.        if (dir1 == dir)      // rebalancing by one rotation
  63.          { rotation(p,u,dir1);
  64.            p->set_bal(red);
  65.            u->set_bal(black);
  66.            break;
  67.           }       
  68.        else
  69.         { double_rotation(p,u,v,dir1);
  70.           p->set_bal(red);
  71.           v->set_bal(black);
  72.           break;
  73.          }
  74.    }
  75.  
  76. }
  77.  
  78.  
  79.  
  80. void rb_tree::del_rebal(rb_tree_item w, rb_tree_item p)
  81. {
  82.   // precondition:    p is removed inner node
  83.   //                  w is remaining child of p (already linked to parent u)
  84.   //                  w != root
  85.  
  86.  
  87.  
  88.   if (p->get_bal()==red) return;  // case 1 : nothing to do
  89.  
  90.   if (w->get_bal()==red)          // case 2
  91.   { w->set_bal(black); 
  92.     return; 
  93.    } 
  94.  
  95.  
  96.   rb_tree_item u = w->parent;
  97.   int dir = (w == u->child[left]) ? left : right;
  98.  
  99.   while (true)
  100.   {
  101.     rb_tree_item w = u->child[1-dir];
  102.   
  103.     // situation: black height of subtree rooted at black node 
  104.     // v = u->child[dir] is by one too small, w = sibling of v
  105.     //
  106.     // => increase black height of v or "move" v towards the root
  107.     //
  108.     //                          |                         |
  109.     //                          u                         u
  110.     //           dir=left:     / \        dir=right:     / \
  111.     //                        /   \                     /   \
  112.     //                       v     w                   w     v
  113.     //                            / \                 / \
  114.     //                           /   \               /   \
  115.     //                          y     x             x     y
  116.    
  117.   
  118.     if ( w->get_bal()==black )                    // case 2: v and w are black
  119.       { rb_tree_item y = w->child[1-dir];
  120.         if ( y->get_bal()==red )                  // case 2.b 
  121.            { rotation(u,w,1-dir);
  122.              w->set_bal(u->get_bal());
  123.              u->set_bal(black);
  124.              y->set_bal(black);
  125.              break;
  126.             }
  127.         else   
  128.            if ( (y=w->child[dir])->get_bal()==red ) // case 2.c 
  129.               { double_rotation(u,w,y,1-dir);
  130.                 y->set_bal(u->get_bal());
  131.                 u->set_bal(black);
  132.                 break;
  133.               }
  134.            else 
  135.               if ( u->get_bal()==red )     // case 2.a2
  136.                  { w->set_bal(red);
  137.                    u->set_bal(black);
  138.                    break; 
  139.                   }
  140.               else                        // case 2.a1
  141.                  { rotation(u,w,1-dir);
  142.                    u->set_bal(red);
  143.                    if ( w == root() )
  144.                       break;
  145.                    else // the only non-terminating case
  146.                       { u = w->parent;
  147.                         dir = (w == u->child[left]) ? left : right;
  148.                        }
  149.                   }
  150.       }     
  151.     else                                  // case 3: v ist black, w ist red
  152.       { rb_tree_item x = w->child[dir];
  153.         rb_tree_item y;
  154.         if ( x->child[1-dir]->get_bal()==red )          // case 3.b
  155.           { double_rotation(u,w,x,1-dir);
  156.             w->child[dir]->set_bal(black);
  157.             break;
  158.            }
  159.         else 
  160.            if ( (y = x->child[dir])->get_bal()==red )   // case 3.c
  161.              { rotation(x,y,dir);
  162.                w->child[dir] = y; 
  163.                double_rotation(u,w,y,1-dir);
  164.                y->set_bal(black);
  165.                break;
  166.               }
  167.            else                                     // case 3.a 
  168.              { rotation(u,w,1-dir);
  169.                w->set_bal(black);
  170.                x->set_bal(red);
  171.                break;
  172.               }
  173.        }
  174.   
  175.    } /* end of loop */
  176.  
  177. }
  178.  
  179.